1. Field of Invention
The present invention relates generally to network systems. More particularly, the present invention relates to enabling a path between a source and a destination to be automatically chosen such that the number of potential single failure points may be minimized.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. To address the demand for data communication services, the use of optical networks, such as a synchronous digital hierarchy (SDH) network or a synchronous optical network (SONET), is becoming more prevalent. A SONET network is an example of a time division multiplexed (TDM) network. TDM networks generally allocate single lines to be used amongst multiple users, or customers of data communication services. The single lines may each be divided into slots of time during which each user has access to the single lines.
Providers of network services typically aim to provide a large variety of service level agreements to customers in an effort to more effectively meet the needs of the customers. Service level agreements generally provide circuit paths that minimize the use of network resources while meeting the requirements of a service level.
Typically, optical networks provided by service providers include a mix of protection schemes. Within a given network, there is often some combination of 2-fiber bi-directional line switched rings (BLSRs), 4-fiber BLSRs, links with 1+1 protection, and uni-directional path switched rings (UPSRs). A circuit path through a network may include a combination of links with different kinds of protection. In general, any time there is a transition in a circuit path between different protection schemes, the node at which the transition essentially occurs is considered to be a single point of failure.
Many network administrators are turning to the use of automated path computation algorithms to use in determining circuit paths through a network, since the manual routing of circuit paths is often time-consuming and, hence, inefficient. Typical automated algorithms which are used to compute circuit paths through a network are based on shortest path first logic. In other words, a best path through a network is often considered to be the path with the least number of hops, or the path which passes through the fewest number of nodes. To identify the shortest path through a network, many path computation algorithms account for both the number of hops included in the path and the cost of each link included in the path. In other words, the number of hops included in a path and the cost of each link included in the path are routing metrics which are used in the determination of circuit paths through a network.
FIG. 1a is a diagrammatic representation of a network in which multiple paths are available between a source node and a destination node. A network 100 includes nodes 104, which may be routers, servers, or substantially any other network element. Nodes 104 are in communication with one another over links 110 of an inner BLSR ring, e.g., an inner 2-fiber BLSR ring or an inner 4-fiber BLSR ring, and links 114 of an outer BLSR ring, e.g., an outer 2-fiber BLSR ring or an outer 4-fiber BLSR ring. Node 104a is a source node, or a start node, for a circuit path through network 100, while node 104c is a destination node, or an end node, for the circuit path through network 100.
Assuming that a circuit path from node 104a to node 104c is preferably to include intermediate node 104b, then there may be four potential circuit paths. A first path 118 from node 104a to node 104c utilizes link 114a and link 114b of the outer BLSR ring, while a second path 122 from node 104a to node 104c utilizes link 110a and link 110b of the inner BLSR ring. A third path 126 from node 104a to node 104c includes link 114a of the outer BLSR ring and link 110b of the inner BLSR ring. It should be appreciated that a fourth path (not shown) from node 104a to node 104c includes link 110a of the inner BSLR ring and link 114b of the outer BLSR ring. However, since such a path is similar to third path 126 in that it also includes a link from the inner BLSR ring and a link from the outer BLSR ring, such a path has not been shown for ease of illustration.
Each of paths 118, 122, 126 has two hops, and the cost of the links included in each path 118, 122, 126 is substantially the same. Hence, each of paths 118, 122, 126 may be considered to be the shortest path from node 104a to node 104c which includes node 104b. 
Though paths 118, 122, 126 may each be considered to be the shortest path from node 104a to node 104c, paths 118, 122, 126 have different path protection characteristics. By way of example, if node 104b fails, not all of paths 118, 122, 126 are protected such that a signal may still be routed. With reference to FIG. 1b, the ramifications of the failure of node 104b will be described. When node 104b fails, or is otherwise taken off line, then if a circuit path from node 104a to node 104c which is arranged to pass through node 104b is path-protected, information may continue to be sent from node 104a to node 104c. By way of example, since a first path 118 of FIG. 1a utilizes link 114a and link 114b of an outer BLSR ring, first path 118 is protected by alternate path 138 which includes link 114d and link 114c of the outer BLSR ring. Hence, when node 104b fails, alternate path 138 may be used to send information from node 104a to node 104d in lieu of path 118 of FIG. 1a. Similarly, since a second path 122 of FIG. 1a utilizes link 10a and link 10b of an inner BLSR ring, second path 122 is protected by alternate path 132 which includes link 110d and link 110c. 
A third path 126 of FIG. 1a, however, is not path-protected from a failure of node 104b. That is, there is no alternate path which enables signals which are intended to pass on third path 126 of FIG. 1a to be successfully routed from node 104a to node 104c if node 104b fails. Since third path 126 includes link 114a and link 110b, which are parts of different BLSR rings, though third path 126 is line-protected, third path 126 is not protected from a failure of node 104b. 
Path computation algorithms generally do not account for the possibility of path-protection, as path-protection is not quantified as a routing metric. As a result, a circuit path which does not have path-protection may be selected as the path to be used between a source and a destination when comparable circuit paths which have path-protection are available. When path-protection is an important consideration, the selection of a shortest path which is not path-protected may have significant consequences when an intermediate node within the shortest path fails.
By way of example, FIG. 2 is a diagrammatic representation of a network in which a shortest available path may not be the most desirable path. Within a network 200 that includes nodes 202, the shortest path between source node 202a and destination node 202c includes a link 206a and a link 206b. A path that includes link 206a and link 206b is path-protected by an alternate path that includes link 206d and link 206c. Typically, a path computation algorithm which is arranged to identify a shortest path between source node 202a and destination node 202c will identify the path that includes link 206a and link 206b as the best path, particularly if link 206d and link 206c are identified as having a relatively high cost or if node 202b is desired as an intermediate node if possible.
If link 206b is unavailable, e.g., if link 206b does not have any available bandwidth, and links 206d, 206c are considered to have relatively high costs or if node 202d is desired as an intermediate node if possible, then a path computation algorithm may identify a path which includes link 206a, link 206g, and link 206h as the shortest path between source node 202a and destination node 202c. While a path which includes link 206a, link 206g, and link 206h may be the shortest available path between source node 202a and destination node 202c, such a path is not path-protected. A path which includes links 206e-h is not the shortest available path when link 206b is effectively unavailable, though such a path is path-protected. Since the path which includes links 206e-h is not identified by typical path computation algorithms as the best path between source node 202a and destination node 202c, even if a path with path-protection may be considered to be more important than a shortest path, the path selected by typical path computations algorithms may not be path-protected.
Therefore, what is needed is an automated system which enables path-protection to be considered as a criterion when a path between a source and a destination is to be computed. That is, what is desired is a path computation algorithm which automatically enables path-protection to be used as a routing metric when it comes to the selection of circuit paths through a network.